//
//  test.c
//  堆的实现
//
//  Created by 仲7 on 2025/5/17.
//
#include"heap.h"

//复习冒泡排序
//O(n^2)
void BubbleSort(int* arr,int n)
{
    for (int i = 0; i < n-1; i++) {
        int flag = 0;//判断内循环后原数组是否已经为升序
        for (int j = 0; j < n-1-i; j++) {
            if(arr[j] > arr[j+1])
            {
                Swap(&arr[j],&arr[j+1]);
            }
            flag++;
        }
        if(flag == 0)//内循环中，没有进行交换，说明原数组已是升序，无需进行下一趟外循环，直接跳出
        {
            break;
        }
    }
}
//堆排序
void HeapSort(int* arr,int n)//传节点数用于防止向下调整算法越界
{
    //堆排序（比如排降序——小堆）
    //1.先用向下调整算法建小堆
    //O(N*logN)
    for (int i = (n - 2)/2;  i >= 0; i--)//i要大于等于零，因为最后在根节点也会向下调整
    {
        Adjustdown(arr, i, n);
    }
    //也可以用向上调整算法建小堆
    //for (int i = 0; i < n; i++) {
    //    Adjustup(arr, i);
    //}
    //2.建堆成功后，再依旧用向下调整筛选最值排到最后一位
    //O(N*logN)
    int end = n-1;//建立有效值，每排一次最值，就减一，直到排序完成（end 减为零）
    while(end > 0)
    {
        Swap(&arr[0], &arr[end]);
        Adjustdown(arr, 0, end);//将交换后的二叉树重新调整为小堆
        end--;//每次将最值移动到最后一位后，将有效值大小减即可。
    }
}
void Testo1(void)
{
    HP hp;
    HpInit(&hp);
    for(int i = 0;i < 6;i++)
    {
        int arr[6] = {17,20,10,13,19,15};
        HPPush(&hp, arr[i]);
    }
    for (int i = 0; i <6; i++) {
               printf("%d ",hp.arr[i]);
           }
    printf("\n");
    //for (int i = 0; i < 1; i++) {
    //    HPPop(&hp);
    //}
    //for (int i = 0; i <6; i++)
    //{
      //         printf("%d ",hp.arr[i]);
    //}
    while (!HPEmpty(&hp)) {
        printf("%d ",HPTop(&hp));
        HPPop(&hp);
    }// 取堆顶元素打印，并非是按原本堆的编号打印的，由于出堆后向下调整算法，结果可能不同
    int arr[6] = {17,20,10,13,19,15};
    //BubbleSort(arr, 6);//排序（升序）成功
    //测试堆排序
    HeapSort(arr, 6);//测试（降序）成功
    HpDestroy(&hp);
    
}
int main(void)
{
    
    Testo1();
    return 0;
}
